Optimal Cooperation and Submodularity for Computing Potts' Partition Functions with a Large Number of State

摘要

The partition function of the q-state Potts model with random ferromagneticcouplings in the large-q limit is generally dominated by the contribution of asingle diagram of the high temperature expansion. Computing this dominantdiagram amounts to minimizing a particular submodular function. We provide acombinatorial optimization algorithm, the optimal cooperation algorithm, whichworks in polynomial time for any lattice. Practical implementation and thespeed of the method is also discussed.